package edu.cityu.cs.hk.datastructures;
import java.util.Iterator;

/**
  * An realization of a graph according to adjacency list structure.
  *
  * @author Roberto Tamassia, Eric Zamore
  */

public class AdjacencyListGraph implements Graph {
  protected NodeList V;	// container for vertices
  protected NodeList E;	// container for edges
  /** Default constructor that creates an empty graph */
  public AdjacencyListGraph() {
    V = new NodeList();
    E = new NodeList();
  }
  /** Return an iterator over the vertices of the graph */
  public Iterator vertices() {
    return V.elements();
  }
  /** Return an iterator over the edges of the graph */
  public Iterator edges() {
    return E.elements();
  }
  /** Replace the element a given position (vertex or edge) with a new
      element and return the old element */
  public Object replace(Position p, Object o)
    throws InvalidPositionException {
    MyPosition pp = checkPosition(p);
    Object temp = p.element();
    pp.setElement(o);
    return temp;
  }
  /** Return an iterator over the edges incident on a vertex */
  public Iterator incidentEdges(Vertex v)
    throws InvalidPositionException {
    MyVertex vv = checkVertex(v);
    return vv.incidentEdges();

  }
  /** Return the endvertices of a edge in an array of length 2 */
  public Vertex[] endVertices(Edge e)
    throws InvalidPositionException {
    MyEdge ee = checkEdge(e);
    return ee.endVertices();
  }
  /** Return the other endvertex of an incident edge */
  public Vertex opposite(Vertex v, Edge e)
    throws InvalidPositionException {
    checkVertex(v);
    MyEdge ee = checkEdge(e);
    Vertex[] endv = ee.endVertices();
    if (v == endv[0])
      return endv[1];
    else if (v == endv[1])
      return endv[0];
    else
      throw new InvalidPositionException("No such vertex exists");
  }
  /** Test whether two vertices are adjacent */
  public boolean areAdjacent(Vertex u, Vertex v)
    throws InvalidPositionException {
    // search the incidence list of the vertex with smaller degree
    Iterator iterToSearch;
    if (degree(u) < degree(v)) {
      iterToSearch = incidentEdges(u);
    }
    else {
      iterToSearch = incidentEdges(v);
    }
    while (iterToSearch.hasNext()) {
      Vertex[] endV = endVertices((Edge) iterToSearch.next());
      // if there exists an edge whose endpoints are u and v
      if ((endV[0] == u && endV[1] == v) || (endV[0] == v && endV[1] == u))
	return true;
    }
    return false;
  }
  /** Insert and return a new vertex with a given element */
  public Vertex insertVertex(Object o) {
    MyVertex vv =  new MyVertex(o);
    Position p = V.insertLast(vv);
    vv.setLocation(p);
    return vv;
  }
  /** Insert and return a new edge with a given element between two
      vertices */
  public Edge insertEdge(Vertex v, Vertex w, Object o)
    throws InvalidPositionException {
    MyVertex vv = checkVertex(v);
    MyVertex ww = checkVertex(w);
    MyEdge ee = new MyEdge(v, w, o);
    Position pv = vv.insertIncidence(ee);
    Position pw = ww.insertIncidence(ee);
    ee.setIncidences(pv, pw);
    Position pe = E.insertLast(ee);
    ee.setLocation(pe);
    return ee;
  }
  /** Remove a vertex and all its incident edges and return the
      element stored at the removed vertex */
  public Object removeVertex(Vertex v)
    throws InvalidPositionException {
    MyVertex vv = checkVertex(v);
    Iterator inc = incidentEdges(v);
    while (inc.hasNext()) {
      MyEdge e = (MyEdge) inc.next();
      if (e.location() != null) // if the edge has not been marked invalid
	removeEdge(e);
    }
    V.remove(vv.location());
    return v.element();
  }
  /** Remove an edge and return its element */
  public Object removeEdge(Edge e)
    throws InvalidPositionException {
    MyEdge ee = checkEdge(e);
    MyVertex[] endv = ee.endVertices();
    Position[] inc = ee.incidences();
    endv[0].removeIncidence(inc[0]);
    endv[1].removeIncidence(inc[1]);
    E.remove(ee.location());
    ee.setLocation(null);	// invalidating this edge
    return e.element();
  }

  // Auxiliary methods

  /** Return the degree of a given vertex */
  public int degree(Vertex v) {
    MyVertex vv = checkVertex(v);
    return vv.degree();
  }

  /** Determines whether a given position is valid. */
  protected MyPosition checkPosition(Position p) 
    throws InvalidPositionException {
    if (p == null || !(p instanceof MyPosition))
      throw new InvalidPositionException("Position is invalid");
    return (MyPosition) p;
  }

  /** Determines whether a given vertex is valid. */
  protected MyVertex checkVertex(Vertex v) 
    throws InvalidPositionException {
    if (v == null || !(v instanceof MyVertex))
      throw new InvalidPositionException("Vertex is invalid");
    return (MyVertex) v;
  }
  
  /** Determines whether a given edge is valid. */
  protected MyEdge checkEdge(Edge e) 
    throws InvalidPositionException {
    if (e == null || !(e instanceof MyEdge))
      throw new InvalidPositionException("Edge is invalid");
    return (MyEdge) e;
  }

  /** Implementation of a decorable position by means of a hash
   * table. */
  protected static class MyPosition 
    extends HashTable implements DecorablePosition {
    /** The element stored at this position. */
    protected Object elem;
    /** Returns the element stored at this position. */
    public Object element() {
      return elem;
    }
    /** Sets the element stored at this position. */
    public void setElement(Object o) {
      elem = o;
    }
  }
  
  /** Returns a string representation of the vertex and edge lists,
   * separated by a newline. */
  public String toString() {
    return V.toString() + "\n" +  E.toString();
  }

  /** Implementation of a vertex for an undirected adjacency list
   * graph.  Each vertex stores its incidence container and position
   * in the vertex container of the graph. */
  protected static class MyVertex extends MyPosition implements Vertex {
    /** Incidence container of the vertex. */
    protected List I; 
    /** Position of the vertex in the vertex container of the graph. */
    protected Position loc;
    /** Constructs the vertex with the given element. */
    MyVertex (Object o) {
      elem = o;
      I = new NodeList();
    }
    /** Return the degree of a given vertex */
    public int degree() {
      return I.size();
    }
    /** Returns the incident edges on this vertex. */
    public Iterator incidentEdges() {
      return I.elements();
    }
    /** Inserts an edge into the incidence container of this vertex. */
    public Position insertIncidence(Edge e) {
      return I.insertLast(e);
    }
    /** Removes an edge from the incidence container of this vertex. */
    public void removeIncidence(Position p) {
      I.remove(p);
    }
    /** Returns the position of this vertex in the vertex container of
     * the graph. */
    public Position location() {
      return loc;
    }
    /** Sets the position of this vertex in the vertex container of
     * the graph. */
    public void setLocation(Position p) {
      loc = p;
    }
    /** Returns a string representation of the element stored at this
     * vertex. */
    public String toString() {
      return elem.toString();
    }
  }

  /** Implementation of an edge for an undirected adjacency list
   * graph.  Each edge stores its endpoints (end vertices), its
   * positions within the incidence containers of its endpoints, and
   * position in the edge container of the graph. */    
  protected static class MyEdge extends MyPosition implements Edge {

    /** The end vertices of the edge. */
    protected MyVertex[] V; 
    /** The positions of the entries for the edge in the incidence
     * containers of the end vertices. */
    protected Position[] I;
    /** The position of the edge in the edge container of the
     * graph. */
    protected Position loc;

    /** Constructs an edge with the given endpoints and elements. */
    MyEdge (Vertex v, Vertex w, Object o) {
      elem = o;
      V = new MyVertex[2];
      V[0] = (MyVertex)v;
      V[1] = (MyVertex)w;
      I = new Position[2];
    }
    /** Returns the end vertices of the edge. There are always two
     * elements in the returned array. */
    public MyVertex[] endVertices() {
      return V;
    }
    /** Returns the positions of the edge in the incidence containers
     * of its end vertices.  The returned array always contains two
     * elements. */
    public Position[] incidences() {
      return I;
    }
    /** Sets the positions of the edge in the incidence containers of
     * its end vertices. */
    public void setIncidences(Position pv, Position pw) {
      I[0] = pv;
      I[1] = pw;
    }
    /** Returns the position of the edge in the edge container of the
     * graph. */
    public Position location() {
      return loc;
    }
    /** Sets the position of the edge in the edge container of the
     * graph. */
    public void setLocation(Position p) {
      loc = p;
    }
    /** Returns a string representation of the edge via a tuple of
     * vertices. */
    public String toString() {
      return "(" + V[0].toString() + "," + V[1].toString() + ")";
    }
  }
}


